package com.zmh.arithmetic.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * n皇后 no.51
 *
 * @author zmh
 * @create 2019-07-31 16:13
 **/
public class NQueens {
    private List<List<String>> resultList = new ArrayList<>();
    private List<Integer> item = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        calcResult(0, n);
        return resultList;
    }

    private void calcResult(int row, int n) {
        if (row == n) {
            return;
        }

        for (int i = 0; i < n; i++) {
            if (isOk(i)) {
//                System.out.println("row : " + row + " colum: " + i);
                item.add(i);
                calcResult(row + 1, n);
                if (row == n - 1) {
                    resultList.add(itemToList(item));
                }
                if (item.size() > 0) {
                    item = item.subList(0, item.size() - 1);
                }
            }
        }
    }

    private boolean isOk(int colum) {
        int length = item.size();
        if (length < 1) {
            return true;
        }
        int leftUp = colum - 1;
        int rightUp = colum + 1;
        for (int i = length - 1; i >= 0; i--) {
            Integer ii = item.get(i);
            if (ii == colum) {
                return false;
            }
            if (leftUp >= 0 && leftUp == ii) {
                return false;
            }
            if (rightUp == ii) {
                return false;
            }
            leftUp--;
            rightUp++;
        }
        return true;
    }

    private List<String> itemToList(List<Integer> item) {
//        System.out.println("item size " + item.size());
        List<String> list = new ArrayList<>();
        for (int i : item) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < item.size(); j++) {
                if (i == j) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            list.add(sb.toString());
        }
        return list;
    }

    public static void main(String[] args) {
        NQueens nQueens = new NQueens();
        List<List<String>> lists = nQueens.solveNQueens(4);
        System.out.println(lists.toString());
    }
}
